package listbyorder.access001_100.test5;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 14:23
 */
public class Solution3 {

    // 方法四： 马拉车算法
    public String longestPalindrome(String s) {
        if (s == null || s.equals("") || s.length() < 2) return s;
        int len = s.length();
        char[] chars = new char[2 * len + 1];   // 保证数据的行数为偶数
        for (int i = 0; i < chars.length; i++) {
            if (i % 2 == 0) {
                chars[i] = '#';
            } else {
                chars[i] = s.charAt(i / 2);
            }
        }
        int[] pArr = new int[len * 2 + 1];    // 创建一个数组，存储当前位置的回文半径
        int cur_center = -1;                  // 存放当前最大回文右边界的中心位置
        int pR = -1;                          // 当前的最大回文右边界
        int maxLen = 0;
        int centerIndex = 0;
        // 遍历chs，更新数组
        for (int i = 0; i < chars.length; i++) {
            // 如果当前位置在最大回文右边界里面，则更新
            pArr[i] = pR > i ? Math.max(pR - i, pArr[(2 * cur_center) - i]) : 1;

            // 进行中心扩展之后，更新当前的最大回文右边界和中心位置（先更新边界）
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                cur_center = i;
            }

            // 将当前位置进行中心扩展（然后再中心扩展）
            while (i + pArr[i] < chars.length && i - pArr[i] >= 0) {
                if (chars[i + pArr[i]] == chars[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }

            // 更新结果
            if (pArr[i] > maxLen) {
                maxLen = pArr[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen + 1) / 2; // 起始点的位置
        return s.substring(start, start + maxLen - 1);
    }
}
